; 原题 树形递归解法
(define (count-change amount)
  (cc amount 4))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                      (- kinds-of-coins 1))
                  (cc (- amount
                          (first-denomination kinds-of-coins))
                          kinds-of-coins)))))

(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

; (cc 100 5)
; (+ (cc 100 4) (cc 50 5))
; (+ (+ (cc 100 3) (cc 75 5)) (+ (cc 50 4) (cc 0 5)))
; (+ (+ (+ (cc 100 2) (cc 90 5)) (cc 75 5)) (+ (cc 50 4) (cc 0 5)))


(cc 100 2)
(+ (cc 100 1) (cc 95 2))
(+ (+ (cc 100 0) (cc 95 1)) (+ (cc 95 1) (cc 90 2)))
(+ (+ 0 (+ (cc 95 0) (cc 90 1))) (+ (+ (cc 95 0) (cc 90 1)) (+ (cc 90 1) (cc 85 2))))

(cc 5 1)
(+ (cc 5 0) (cc 4 1))
(+ (cc 5 0) (+ (cc 4 0) (cc 3 1)))
(+ (cc 5 0) (+ (cc 4 0) (+ (cc 3 0) (+ (cc 2 1)))))
(+ (cc 5 0) (+ (cc 4 0) (+ (cc 3 0) (+ (+ (cc 2 0) (+ (cc 1 1)))))))
(+ (cc 5 0) (+ (cc 4 0) (+ (cc 3 0) (+ (+ (cc 2 0) (+ (+ (cc 1 0) (cc 0 1))))))))

(cc 5 2)
(+ (cc 5 1) (cc 0 2))
(+ (+ (cc 5 0) (cc 4 1)) 1n)
(+ (+ (cc 5 0) (cc 4 1)) 1)

(cc 3 2)
(+ (cc 3 1) (cc 2 2))
(+ (+ (cc 3 0) (cc 2 1)) (+ (cc 2 1) (cc 1 2)))

0 2 + 5 1
5 2



(define (count-change amount)
  (cc amount 5 0))

(define (cc amount kinds-of-coins total)
  (cond ((= amount 0) (+ total 1))
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount (- kinds-of-coins 1) total)
                (cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins total)))))

(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))


amount n = amount n - 1 + amount - coins n
amount - coins n = amount n - 2 + amount - 2coins n

; amount n - 2 + amount - 2coins n + amount n - 1

